1.Field of the Invention
The present invention generally relates to multiplex interconnection networks for communications systems, and especially digital communications systems for parallel computers, and, more particularly, to a switching network in which switch connections are used to establish "waiting chains" for ports which desire to communicate with a single port.
2. Description of the Prior Art
High performance computer systems frequently involve the use of multiple central processing units (CPUs), each operating independently, but occasionally communicating with one another or with memory devices when data needs to be exchanged. A switching system, such as a crossbar switch, is used to interconnect CPUs and memory devices. This type of system is illustrated in FIG. 1 which shows a large number of CPUs 10, each operating independently and in parallel with each other. Each of the CPUs 10 occasionally requires access to one of several memories 12. Each CPU has an input/output (I/O) path 14, and each memory device has an I/O path 16. The paths 14 and 16 can be buses and may be duplicated to provide full-duplex communication. Selective connection of an I/O path 14 to an I/O path 16 is performed by a switch 18, such as a crossbar switch.
U.S. Pat. No. 4,605,928 to C. J. Georgiou describes a crossbar switch composed of an array of smaller crossbar switches, each on a separate integrated circuit (IC). U.S. Pat. No. 4,360,045 to C. J. Georgiou describes a controller for the crossbar switch. This particular controller must sequentially service multiple ports requesting connection through the crossbar switch. U.S. Pat. No. 4,635,250 to Georgiou and U.S. Pat. No. 4,875,704 to C. J. Georgiou et al. describe switching systems which uses a one sided cross-point switching matrix for establishing connections between pairs of port adapters in a communication system. The switching matrix controllers of these switching systems can only connect currently available port adapters and cannot establish a waiting queue.
Consider an N.times.N crossbar switch used for full duplex connections between some number M of devices with a total of M.ltoreq.N ports P.sub.1, P.sub.2, . . . , P.sub.M. Suppose port P.sub.i makes a request to be connected with port P.sub.j, but port P.sub.j is currently busy (e.g., it is connected to port P.sub.k). Two alternatives are to have port P.sub.i try again or to have port P.sub.i simply wait until the switch controller(s) indicate that port P.sub.j is free. The latter alternative is sometimes referred to as "camp-on" and is usually obtained by having the controller(s) maintain queues for each busy port. If the switch is large, and especially if it is organized as a modular structure with multiple parallel controller(s), then maintaining wait chains adds to the expense and overhead of the switch. It can also introduce substantial delays in path setup and message initiation. What is needed is a way to alleviate this problem.